package blue_bridge_cup_learning.前缀和;

import java.util.Scanner;

// 蓝桥公园是一个适合夜间散步的好地方，公园可以被视为由 n×m 个矩形区域构成。每个区域都有一盏灯，初始亮度为 a[i][j]。
// 小蓝可以选择一个大的矩形区域，并按下开关一次，这将使得该区域内每盏灯的亮度减少 1，但每个区域内的灯的亮度最多只能减少至 a[i][j]−c。如果此时亮度为 a[i][j]−c，再次按下开关将使得灯的亮度恢复为 a[i][j]。
// 现在小蓝将进行 t 次操作。每次操作他会选择一个矩形区域，该区域的左上角端点为(x1,y1)，右下角端点为(x2,y2)，然后将该区域内所有灯按下 k 次开关。他想知道，在每次操作结束后，该区域内所有灯的总亮度是多少？然后在下一次操作前，他会将公园内 所有灯光恢复初始值。
// 数据保证每盏灯的亮度不会减少至负数。
public class 闪耀的灯光 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = 3, m = 3, c = 3;
        int[][] arr = new int[][] {
                { 14, 14, 17 },
                { 13, 15, 18 },
                { 13, 16, 19 }
        };
        System.out.println("原数组：");
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                System.out.print(arr[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("--------------------------------");
        System.out.println("前缀和数组：");
        int[][] preSum = getSum(arr);
        for (int i = 0; i < preSum.length; i++) {
            for (int j = 0; j < preSum[0].length; j++) {
                System.out.print(preSum[i][j] + "\t");
            }
            System.out.println();
        }
        System.out.println("--------------------------------");
        System.out.println("测试区间和x1:2,y1:2,x2:3,y2:3的区间和为");
        System.out.println(get(preSum, 2, 2, 3, 3));
        int time = 2;
        for (int i = 0; i < time; i++) {
            System.out.println("请输入x1,y1,x2,y2,k");
            int x1 = scan.nextInt();
            int y1 = scan.nextInt();
            int x2 = scan.nextInt();
            int y2 = scan.nextInt();
            int k = scan.nextInt();
            // c次一个循环，c=3时 例如14,15,16,17,14;
            int f = k % (c + 1);
            // 求区间和
            int sum = get(preSum, x1, y1, x2, y2);
            // 求最终的亮度
            System.out.println(sum + f * (x2 - x1 + 1) * (y2 - y1 + 1));
        }
    }

    public static int[][] getSum(int[][] arr) {
        int[][] preSum = new int[arr.length + 1][arr[0].length + 1];
        for (int i = 1; i < preSum.length; i++) {
            for (int j = 1; j < preSum[0].length; j++) {
                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + arr[i - 1][j - 1];
            }
        }
        return preSum;
    }
    // 这个求区间和的方法有以下问题:
    // 1. 参数x1,y1,x2,y2是从1开始的下标,但是我们的原数组arr是从0开始的下标,这会导致计算错误
    // 2. 每次求区间和都要重新构建前缀和数组,这样效率很低
    // 3. 没有对输入参数进行边界检查

    // 正确的求区间和方法应该是:

    public static int get(int[][] arr, int x1, int y1, int x2, int y2) {
        return arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1];
    }
}
